﻿#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

class TrieTreeForDir
{
public:
	TrieTreeForDir(string str);
	TrieTreeForDir* find(string str);
	TrieTreeForDir* add(string str);
	const map<string, TrieTreeForDir*>& GetMap();

private:
	string value;
	map<string, TrieTreeForDir*> treeMap;
};

TrieTreeForDir::TrieTreeForDir(string str)
{
	value = str;
}

TrieTreeForDir* TrieTreeForDir::find(string str)
{
	auto pair = treeMap.find(str);
	if (pair == treeMap.end()) return nullptr;

	return pair->second;
}

TrieTreeForDir* TrieTreeForDir::add(string str)
{
	auto exists = find(str);
	if (!exists)
	{
		exists = new TrieTreeForDir(str);
		treeMap[str] = exists;
	}

	return exists;
}

const map<string, TrieTreeForDir*>& TrieTreeForDir::GetMap()
{
	return treeMap;
}

static void releaseTree(TrieTreeForDir* tree)
{
	auto m = tree->GetMap();
	TrieTreeForDir* subTree;
	for (auto pair = m.begin(); pair != m.end(); pair++)
	{
		subTree = pair->second;
		releaseTree(subTree);
	}

	delete(tree);
}

static void format(TrieTreeForDir* tree, const char* path)
{
#define CUR_LEN 100
	char subStr[CUR_LEN] = { 0 };
	int index = 0;
	int curIndex = 0;
	auto len = strlen(path);
	vector<string> strVec;
	while (index < len)
	{
		if (path[index] == '\\')
		{
			strVec.push_back(subStr);
			memset(subStr, 0, CUR_LEN);
			curIndex = 0;
		}
		else
		{
			subStr[curIndex++] = path[index];
		}

		++index;
	}

	strVec.push_back(subStr);

	string cur;
	TrieTreeForDir* curTree = tree;
	for (auto it = strVec.begin(); it != strVec.end(); it++)
	{
		cur = *it;
		auto existsTree = curTree->find(cur);
		if (existsTree)
		{
			curTree = existsTree;
		}
		else
		{
			curTree = curTree->add(cur);
		}
	}
}

static void printTree(TrieTreeForDir* tree, int layer)
{
	auto m = tree->GetMap();
	if (m.size() == 0) return;

#define INFO_LEN 256
	char info[INFO_LEN];
	int index;
	string val;
	TrieTreeForDir* childTree;
	for (auto pair = m.begin(); pair != m.end(); pair++)
	{
		memset(info, 0, INFO_LEN);
		index = 0;
		for (int i = 0; i < layer * 2; i++)
		{
			info[index++] = ' ';
		}

		childTree = pair->second;
		val = pair->first;
		memcpy(info + index, val.c_str(), val.size());
		printf("%s\n", info);

		printTree(childTree, layer + 1);
	}
}

/**
 * 给你一个字符串类型的数组arr，譬如:
 * String[] arr = {"b\\cst", "d\\", "a\\d\\e", "a\\b\\c"};
 * 把这些路径中蕴含的目录结构给画出来，子目录直接在父目录下面，并比父目录向右进两格，就像这样:
 * a
 *   b
 *     c
 *   d
 *     e
 * b
 *   cst
 * d
 *
 * 同一级的需要按字母顺序排列，不能乱。
 *
 * 思路:
 * 使用前缀树
 */
int main_PrintDirectories()
{
#define ONE_PATH_LEN 100
	char paths[][ONE_PATH_LEN] = {
		"b\\cst",
		"d\\",
		"a\\d\\e",
		"a\\b\\c",
	};

	int count = sizeof(paths) / ONE_PATH_LEN;
	TrieTreeForDir* tree = new TrieTreeForDir("");
	for (int i = 0; i < count; i++)
	{
		format(tree, paths[i]);
	}

	printTree(tree, 0);
	releaseTree(tree);
	return 0;
}